module Arbol23 where

data Arbol23 a b = Hoja a | Dos b (Arbol23 a b) (Arbol23 a b) | Tres b b (Arbol23 a b) (Arbol23 a b) (Arbol23 a b)

{- Funciones para mostrar el Arbol. -}

instance (Show a, Show b) => Show (Arbol23 a b) where
    show x = concatMap (++"\n") (padTree 0 x)

padTree :: (Show a, Show b) => Int -> (Arbol23 a b)-> [String]
padTree i (Hoja x) = [(pad i) ++  (show x)]
padTree i (Dos x a1 a2) = [(pad i) ++  (show x) ] ++ (concatMap (padTree (i + 4)) [a1,a2])
padTree i (Tres x y a1 a2 a3) = [(pad i) ++  (show x) ++ (' ':(show y))] ++ (concatMap (padTree (i + 4)) [a1,a2,a3])

pad:: Int -> String
pad i = replicate i ' '

{- Funciones pedidas. -}


-- Ejercicio 1

-- La función foldA23 provee un mecanismo de recursión estructural sobre árboles 2-3, haciendo pattern matching sobre sus constructores.
-- Los argumentos que acepta son, respectivamente:
  -- + una función para aplicar en caso del constructor no recursivo Hoja
  -- + una función para aplicar en caso del constructor recursivo Dos
  -- + una función para aplicar en caso del constructor recursivo Tres
  -- + el árbol 2-3 sobre el cual efectuar la recursión

foldA23 :: (a -> rt) -> (b -> rt -> rt -> rt) -> (b -> b -> rt -> rt -> rt -> rt) -> Arbol23 a b -> rt
foldA23 f_hoja f_dos f_tres (Hoja x) = f_hoja x
foldA23 f_hoja f_dos f_tres (Dos x a1 a2) = f_dos x (foldA23 f_hoja f_dos f_tres a1) (foldA23 f_hoja f_dos f_tres a2)
foldA23 f_hoja f_dos f_tres (Tres x y a1 a2 a3) = f_tres x y (foldA23 f_hoja f_dos f_tres a1) (foldA23 f_hoja f_dos f_tres a2) (foldA23 f_hoja f_dos f_tres a3)


-- Ejercicio 2

-- La función hojas lista las hojas de un árbol 2-3 (su único argumento) de izquierda a derecha.
-- Para cada hoja devuelve una lista con el valor de la hoja como único elemento.
-- Para cada nodo interno devuelve los resultados de la recursión concatenados (ignorando los valores de los nodos) de izquierda a derecha.

hojas :: Arbol23 a b -> [a]
hojas = foldA23 (:[]) (\_ a1 a2 -> a1 ++ a2) (\_ _ a1 a2 a3 -> a1 ++ a2 ++ a3)

-- La función internos lista los nodos internos de un árbol 2-3 en preorden. Es similar a la función hojas.
-- Para cada hoja devuelve una lista vacía, ignorando el valor de la hoja.
-- Para cada nodo interno devuelve el valor (o los valores, según corresponda) del nodo encabezando la lista resultante de concatenar los resultados de la recursión.

internos :: Arbol23 a b -> [b]
internos = foldA23 (const []) (\x a1 a2 -> x : a1 ++ a2) (\x y a1 a2 a3 -> x : y : a1 ++ a2 ++ a3)

--La función esHoja indica si el árbol 2-3 es una hoja, simplemente haciendo pattern matching sobre su constructor.

esHoja :: Arbol23 a b -> Bool
esHoja (Hoja _) = True
esHoja _ = False


-- Ejercicio 3

-- La función mapA23, aplicada a un árbol 2-3, devuelve un nuevo árbol 2-3 que resulta de aplicar una de dos funciones a cada uno de sus nodos, dependiendo de si es hoja o interno.
-- Para cada nodo, lo reconstruye según su constructor luego de aplicadr la función correspondiente a su valor.

mapA23 :: (a -> c) -> (b -> d) -> Arbol23 a b -> Arbol23 c d
mapA23 f_hoja f_nodo = foldA23 (Hoja . f_hoja) (\x a1 a2 -> Dos (f_nodo x) a1 a2) (\x y a1 a2 a3 -> Tres (f_nodo x) (f_nodo y) a1 a2 a3)

--Ejemplo de uso de mapA23.
--Incrementa en 1 el valor de las hojas.

incrementarHojas :: Num a => Arbol23 a b -> Arbol23 a b
incrementarHojas = mapA23 (+1) id


-- Ejercicio 4

-- Trunca el Arbol hasta un determinado nivel. Cuando llega a 0, reemplaza el resto del Arbol por una hoja con el valor indicado.
-- Funciona para Arboles infinitos.

-- Versión con recursión explícita
-- truncar :: a -> Integer -> Arbol23 a b -> Arbol23 a b
-- truncar v 0 a23 = Hoja v
-- truncar v n a23 = case a23 of
					-- Hoja h				-> Hoja h
					-- Dos x a1 a2			-> Dos x (truncar v (n - 1) a1) (truncar v (n - 1) a2)
					-- Tres x y a1 a2 a3 	-> Tres x y (truncar v (n - 1) a1) (truncar v (n - 1) a2) (truncar v (n - 1) a3)

truncar :: a -> Integer -> Arbol23 a b -> Arbol23 a b
truncar trunc_val nivel a23 = foldA23 truncar_hoja truncar_dos truncar_tres a23 trunc_val nivel

-- Estas tres funciones auxiliares (utilizadas para foldear) tienen el mismo comportamiento en general:
-- si el nivel donde están siendo evaluadas debe ser truncado, retornan la Hoja con el valor truncado
-- en caso contrario rearman el árbol (cada función depende de qué tipo de nodo está evaluando) con la recursión sobre sus hijos (si no es una Hoja)

truncar_hoja :: a -> a -> Integer -> Arbol23 a b
truncar_hoja val trunc_val niveles_restantes
										|niveles_restantes > 0  = mismo
										|otherwise 				= Hoja trunc_val
	where
		mismo = Hoja val

truncar_dos :: b -> (a -> Integer -> Arbol23 a b) -> (a -> Integer -> Arbol23 a b) -> a -> Integer -> Arbol23 a b
truncar_dos val fRec1 fRec2 trunc_val niveles_restantes
													|niveles_restantes > 0  = mismo
													|otherwise 				= Hoja trunc_val
	where
		mismo = Dos val recA1 recA2
		recA1 = fRec1 trunc_val (niveles_restantes - 1)
		recA2 = fRec2 trunc_val (niveles_restantes - 1)

truncar_tres :: b -> b -> (a -> Integer -> Arbol23 a b) -> (a -> Integer -> Arbol23 a b) -> (a -> Integer -> Arbol23 a b) -> a -> Integer -> Arbol23 a b
truncar_tres val1 val2 fRec1 fRec2 fRec3 trunc_val niveles_restantes
																	|niveles_restantes > 0  = mismo
																	|otherwise 				= Hoja trunc_val
	where
		mismo = Tres val1 val2 recA1 recA2 recA3
		recA1 = fRec1 trunc_val (niveles_restantes - 1)
		recA2 = fRec2 trunc_val (niveles_restantes - 1)
		recA3 = fRec3 trunc_val (niveles_restantes - 1)


-- Ejercicio 5

-- Evalúa las funciones tomando los valores de los hijos como argumentos.
-- En el caso de que haya 3 hijos, asocia a izquierda.
evaluar :: Arbol23 a (a -> a -> a) -> a
evaluar = foldA23 id (\op t1 t2 -> op t1 t2) (\op1 op2 t1 t2 t3 -> op2 (op1 t1 t2) t3)


{- Arboles de ejemplo. -}
arbolito1::Arbol23 Char Int
arbolito1 = Tres 0 1
	      (Dos 2 (Hoja 'a') (Hoja 'b'))
	      (Tres 3 4 (Hoja 'c') (Hoja 'd') (Dos 5 (Hoja 'e') (Hoja 'f')))
	      (Dos 6 (Hoja 'g') (Dos 7 (Hoja 'h') (Hoja 'i')))

arbolito2::Arbol23 Int Bool
arbolito2 = Dos True (Hoja (-1)) (Tres False True (Hoja 0) (Hoja (-2)) (Hoja 4))

arbolito3 :: Arbol23 Int (Int -> Int -> Int)
arbolito3 = Dos (+) (Tres (*) (-) (Hoja 1) (Hoja 2) (Hoja 3)) (incrementarHojas arbolito3)

--Ejemplos:
--internos arbolito1 = [0,1,2,3,4,5,6,7]
--hojas arbolito1 = "abcdefghi"
--hojas (incrementarHojas arbolito2) = [0,1,-1,5]
--internos arbolito2 = [True,False,True]
--take 10 (hojas arbolito3) = [1,2,3,2,3,4,3,4,5,4]
--hojas (truncar 0 6 arbolito3) = [1,2,3,2,3,4,3,4,5,4,5,6,0,0,0,0,0]
--evaluar (truncar 0 6 arbolito3) = 22 = (1*2-3)+(2*3-4)+(3*4-5)+(4*5-6)
